/************************************
BigInt
BigInt.cpp - Implementation file
Calculator for large integers.
CS 133 - Parallel Programming
Professor: Adam Kaplan
Due: 6/3/2011
Collaborators:
Ben Harounian
Justin Kiang
Akhil Rangaraj
************************************/
#include "BigInt.h"
#include <string>
#include <string.h>
using namespace std;



/***** Definitions *****/


/*** Constructors ***/

// Default Constructor
BigInt::BigInt()
{
    // Initialize private variables
    // Set 1 thread default
    numThreads = 1;

    // Clear container, create BigAssData element
    decimalContainer.clear();
    binaryContainer.clear();
    
    
    decimalContainer.push_back("0");
    binaryContainer.push_back(0);
}// End default constructor


// Specific Constructor - Takes String
BigInt::BigInt(const std::string &str)
{
    // Call specific constructor
    *this = BigInt(str, 1);
}// End specific constructor


// Specific Constructor - Takes String and Number of Threads
/* USER HAS TO CHECK MAX_THREADS BEFORE SETTING PRIVATE VARIABLE */
BigInt::BigInt(const std::string &str, const int threads)
{
    // Initialize private variables
    string quotient = "";
    string binary = "";
    string transient = str;
    string remainder = "";
    decimalContainer.clear();
    binaryContainer.clear();
    
    do {
        
        remainder = divideBy2(transient,quotient);
        transient = quotient;
      
       binary = remainder+binary;
   }while(strcmp(transient.c_str(),"0") && strcmp(transient.c_str(),"1"));
cout << " got past this part" <<endl;
   if(!strcmp(remainder.c_str(),"1"))
       binary = binary+remainder;
    int binaryCounter = 0;
     const char* binaryCstr = binary.c_str();
     string tempBinary ="";
     while(*binaryCstr !='\0')
     {
          tempBinary += *(binaryCstr++);   //add binary digit to string
          binaryCounter++;
          if(binaryCounter ==32)
              {
                  binaryCounter=0;
                  int herples=  (int) bitset<32>(tempBinary).to_ulong();
                  binaryContainer.push_back(herples);
                  tempBinary="";
              }
     }// End while
    // Set numberof threads
    numThreads = threads;
	string str2 = string(str);
    string::reverse_iterator rit;
     string temp="";
         int digitCounter =0;
    for(rit = str2.rbegin(); rit< str2.rend(); rit++)
    {
            temp += *rit;
            digitCounter++;
             if(digitCounter ==5 || rit == str2.rend()-1)
                {
                    decimalContainer.push_back(string(temp.rbegin(), temp.rend()));
                    temp="";
                        digitCounter =0;
                }
    }
}// End specific constructor


// Copy Constructor
BigInt::BigInt(const BigInt &another)
{
    // Initialize private variables
    decimalContainer = vector<string>(another.decimalContainer);
    binaryContainer = vector<int>(another.binaryContainer);
    // Set numberofThreads
    numThreads = another.numThreads;

}// End copy constructor


// Specific Constructor - Takes Integer
BigInt::BigInt(const int val)
{
    // Initialize private variables
    std::string temp = "";
    std::stringstream out;

    // Read val to stringstream, parse int
    out << val;
    temp = out.str();

    // Call specific constructor
    *this = BigInt(temp, 1);
}// End specific constructor





/*** Operators ***/

/* Arithmetic Operations */


// Operator+ Overloading
const BigInt BigInt::operator+ (const BigInt &right) const
{
    // Make a copy, add the right hand side, return
    return BigInt(*this) += right;
}// End operator+ overloading


// Operator* Overloading
const BigInt BigInt::operator* (const BigInt &right) const
{
    // Make a copy, multiply by the right hand side, return
    return BigInt(*this) *= right;
}// End operator* overloading


/* Bitwise Operations */


// Operator| Overloading
const BigInt BigInt::operator| (const BigInt &right) const
{
    // Make a copy, OR with the right hand side, return
    return BigInt(*this) |= right;
}// End operator| overloading


// Operator^ Overloading
const BigInt BigInt::operator^ (const BigInt &right) const
{
    // Make a copy, XOR with the right hand side, return
    return BigInt(*this) ^= right;
}// End operator^ overloading


// Operator& Overloading
const BigInt BigInt::operator& (const BigInt &right) const
{
    // Make a copy, AND with the right hand side, return
    return BigInt(*this) &= right;
}// End operator& overloading


// Operator! Overloading
/* PROBLEM WITH FLIPPING THE LAST SET OF BITS */
BigInt BigInt::operator! ()
{
    // Flip all the bits
    // Declare, initialize variables
    std::stringstream out;
    size_t size = this->binaryContainer.size();

    // Loop and flip bits in the bit array
    #pragma omp parallel for 
    for (size_t i = 0; i < size; i++)
    {
        // Flip bits
        this->binaryContainer[i] = !this->binaryContainer[i];

    }// End for
    //we need to update the ddecimal representation
    return *this;
}// End operator! overloading


/* Assignment Operations */


// Operator= Overloading
BigInt& BigInt::operator= (BigInt right)
{
    // Only allocate if two objects aren't equal
    if (this != &right)
    {
        // Declare, initialize variables


        // Assign numThreads
        numThreads = right.numThreads;
       decimalContainer = vector<string>(right.decimalContainer);
           binaryContainer = vector<int>(right.binaryContainer);
}
    return *this;
}// End operator= overloading


/* Compound Assignment Operations */


// Operator+= Overloading
    BigInt& BigInt::operator+= (const BigInt &right)
{
    // Declare, initialize variables
    size_t this_size = this->decimalContainer.size();
    size_t right_size = right.decimalContainer.size();

    // Find out which size is larger
    bool this_is_bigger = (this_size > right_size);
    bool right_is_bigger = (right_size > this_size);
    size_t container_size = std::max(this_size, right_size);
    size_t loop_size = std::min(this_size, right_size);
    BigInt result;
    // Create arrays terrible names
    int* arr0 = new int[container_size];
    int* arr1 = new int[container_size];
    int* over = new int[container_size];
    

    //std::cout << "Loop: " << loop_size << " This: " << this_size << " Right: " << right_size << " Container: " << container_size << std::endl;


    // Variables for iterating
    int i = 0;
    std::string l0;
    std::string l1;
    std::stringstream out;
    std::stringstream zero;
    std::stringstream one;
    std::stringstream final;
    result.decimalContainer.resize(container_size);

    // Start parama omp parallel
    #pragma omp parallel
    { 

        // Perform Step 1 of Calculation
        // ADD the values that both share    
        #pragma omp for
        for (i=0; i < loop_size; i++)
        {
            // Add values, store into array
            arr0[i] = atoi(this->decimalContainer[i].c_str()) + atoi(right.decimalContainer[i].c_str());
            arr1[i] = arr0[i]+1;

            //std::cout << "Arr0[" << i << "] = " << arr0[i] << " and it should be " << this->container[i].binaryData << " + " << right.container[i].binaryData << std::endl;
    
            // Store string representations of additions
            zero << arr0[i];
            l0 = zero.str();
            zero.str("");
            one << arr1[i];
            l1 = one.str();
            one.str("");
            
            // Assign overflow
            // Undecided
            if (l0.size() == 5 && l1.size() == 6) 
            {
                over[i]=2;
            }// End if
            
            // Overflow
            else if (l0.size() == 6) 
            {
                over[i]=1;
            }// End else if
            
            // No overflow
            else 
            {
                over[i]=0;
            }// End else  
        }// End for
        
    
        // ADD the extra values
        // Copy the rest from this
        if (this_is_bigger)
        {
            //std::cout << "WERE HERE!\n";
            // ADD other values
//            #pragma omp for
            for (i = loop_size; i < container_size; i++)
            {
                arr0[i] = atoi(this->decimalContainer[i].c_str());
                arr1[i] = arr0[i]+1;
                
                // Store string representations of additions
                zero << arr0[i];
                l0 = zero.str();
                zero.str("");
                one << arr1[i];
                l1 = one.str();
                one.str("");
                
                // Assign overflow
                // Undecided
                if (l0.size() == 5 && l1.size() == 6) 
                {
                    over[i]=2;
                }// End if
                
                // Overflow
                else if (l0.size() == 6) 
                {
                    over[i]=1;
                }// End else if
                
                // No overflow
                else 
                {
                    over[i]=0;
                }// End else
            }// End for
        }// End if
    
        // Copy the rest from right
        else if (right_is_bigger)
        {
            //std::cout << "WERE HERE!\n";
            // ADD other values
//            #pragma omp for
            for (i = loop_size; i < container_size; i++)
            {
                arr0[i] = atoi(right.decimalContainer[i].c_str());
                arr1[i] = arr0[i]+1;
                
                // Store string representations of additions
                zero << arr0[i];
                l0 = zero.str();
                zero.str("");
                one << arr1[i];
                l1 = one.str();
                one.str("");
                
                // Assign overflow
                // Undecided
                if (l0.size() == 5 && l1.size() == 6)  
                {
                    over[i]=2;
                }// End if
                
                // Overflow
                else if (l0.size() == 6) 
                {
                    over[i]=1;
                }// End else if
                
                // No overflow
                else 
                {
                    over[i]=0;
                }// End else
            }// End for
        }// End else
    
    
       #pragma omp single
        {
            // Perform Step 2 Of Calculation
            for (i = 0; i < container_size; i++)
            {
                // Ignore first iteration
                if (i != 0)
                {
                    // Overflow
                    if (over[i] == 1)
                    {
                        arr0[i] = arr1[i];
                    }// End if
                
                    // Change overflow bits when needed
                    else if (over[i] == 2)
                    {
                        if (over[i-1] == 1)
                        {
                            arr0[i] = arr1[i];
                            over[i] = over[i-1];            
                        }// End if            
                    }// End if
                }// End if        
            }// End for
        }//End pragma omp single
    
     
        // Perform Step 3 of Calculation - Copy into new BigInt
        #pragma omp for
        for (i = 0; i < container_size; i++)
        {
            // Store values into result
            if (over[i])
            {
                final.str("");
                final << arr0[i]-100000;
                result.decimalContainer[i] =  final.str();       
            }// End if
    
            else
            {
                final.str("");
                final << arr0[i];
                result.decimalContainer[i] =  arr0[i];      
            }// End else
            
            // Set other values
            //final.str("");
            //result.container[i].bitArray = (int) result.container[i].binaryData;
            //std::cout << "Binary data for each value at " << i << ": " << (int) result.container[i].binaryData << std::endl;
            //std::cout << "Stringstream data for each value at " << i << " (before flush): " << final.str() << std::endl;
            //final.str("");          
            //final << (int) result.container[i].binaryData;
            //result.decimalContainer[i] = final.str();  
            //std::cout << "String data for each value at " << i << ": " << result.container[i].data << std::endl;
            //final.str("");
         }// End for            


        // If overflow, we need to add another BigAssData element to the vector
        if (over[container_size - 1] == 1)
        {
            //BigAssData temp;
            //temp.binaryData = 1;
            //temp.bitArray[0] = 1;
            //temp.data = "1";
            // Insert BigAssData element in front of container
            //container.insert(container.begin(), temp);
    
            // Push BigAssData element to back of container
	#pragma omp critical
	{
            result.decimalContainer.push_back(string("1"));
	}
        }// End if


    }// End pragma omp parallel    

    *this = result;
    return *this;
}// End operator+= overloading


// Operator*= Overloading
BigInt& BigInt::operator*= (const BigInt &right)
{
    // TO DO:
    // My thoughts:
    // For the following calculation     1246
    // we can make a BigInt for      x2378
    // the result of each calculation, and
    // store these in an array of BigInts
    // ie: array[0] would have 1246 * 8
    // ie: array[1] would have 1246 * 7 * 10
    // ie: array[2] would have 1246 * 3 * 100
    // IE: array[i] would have TOP_NUMBER * ith digit in BOTTOM_NUMBER * 10^i
    // We can do these in parallel, and then add up (operator+) the resulting
    // BigInts in the array in parallel as well.
    // BAM!


    // Algorithm
    // We're going to assume that this is below and right is above
    // Take the size of this and create a new BigInt for each digit in this
    // Make an array of BigInts with the length equal to the size of this
    // Multiply each digit in this by all of right and by a power of 10 (addition in for loop)
    // Add each element in the array together
    // Return the result

    // Declare, initialize variables
    std::string arr_string = this->toString();
    size_t arr_siz = arr_string.size();
    BigInt* arr = new BigInt[arr_siz];
    BigInt* result_arr = new BigInt[arr_siz];
    BigInt result;
    std::string temp;
    //std::cout << "Arr_siz = " << arr_siz << "\n";

    //std::cout << "ARR_STRING is this: +" << arr_string << "+\n";


    // Loop and populate the array of BigInts
    // the string "12345" will be [5, 4, 3, 2, 1]
    //std::cout << "****************FOR LOOP 1****************\n";
    for (int i = arr_siz - 1; i >= 0; i--)
    {
        //std::cout << "i = " << i << " and arr_siz - i - 1 = " << (arr_siz - i - 1) << " and arr_string[" << i << "] is " << arr_string[i] << "\n";
        // Create BigInt objects
        temp = arr_string[i];
        arr[arr_siz - i - 1] = BigInt(atoi(temp.c_str()));
        //std::cout << "The object at " << arr_siz - i - 1 << " has a value of " << arr[arr_siz - i - 1].toString() << "\n";
        result_arr[i] = BigInt(0);
    }// End for
    //std::cout << "****************END LOOP 1****************\n";

    // Loop and calculate the multiplication by doing a bunch of additions
    //std::cout << "****************FOR LOOP 2****************\n";
           //can parallelize
           #pragma omp parallel for
    for (int i = 0; i < arr_siz; i++)
    {
        // Store number 5..4..3..2..1, multiply by 10^i
        int loop_num = atoi(arr[i].decimalContainer[0].c_str());
        loop_num *= (int) pow((double) 10, i);
	#pragma omp critical 
{
       std::cout << "i is " << i << " and loop_num is " << arr[i].decimalContainer[0] << "*" << pow((double) 10, i) << " or " << loop_num << "\n";
        }
        // Calculate each individual multiplication problem
        #pragma omp parallel for 
        for (int j = 0; j < loop_num; j++)
        {
            // 5 * 10^0 * right = result_arr[0]
            // 4 * 10^1 * right = result_arr[1]
            result_arr[i] += right;
            //std::cout << "This is the current result after adding right: " << result_arr[i].toString() << "\n";
        }// End for
    }// End for
    std::cout << "****************END LOOP 2****************\n";

    // Loop through and add each element in the result_arr to result
    for (int i = 0; i < arr_siz; i++)
    {
        result += result_arr[i];
    }// End for


    *this = result;
    return *this;
}// End operator*= overloading


// Operator|= Overloading
BigInt& BigInt::operator|= (const BigInt &right)
{
    // Declare, initialize variables
    size_t this_size = this->binaryContainer.size();
    size_t right_size = right.binaryContainer.size();

    // Find out which size is larger
    bool this_is_bigger = this_size > right_size;
    size_t container_size = (this_size > right_size) ? this_size : right_size;
    size_t loop_size = (this_size < right_size) ? this_size : right_size;

    // Variables for iterating
    int i = 0;
    std::stringstream out;
    BigInt result;
    result.binaryContainer.resize(container_size);

    // OR the values that both share
    #pragma omp parallel for
    for (i=0; i < loop_size; i++)
    {
        result.binaryContainer[i] = this->binaryContainer[i] | right.binaryContainer[i];
    }// End for

    // OR the extra values
    // Copy the rest from this
    if (this_is_bigger)
    {
        #pragma omp parallel for
        for (i = loop_size; i < this_size; i++)
        {
            result.binaryContainer[i] = this->binaryContainer[i];
        }// End for
    }// End if

    // Copy the rest from right
    else
    {
        for (i = loop_size; i < right_size; i++)
        {
            result.binaryContainer[i] = right.binaryContainer[i];
        }// End for
    }// End else    

    *this = result;
    return *this;
}// End operator|= overloading


// Operator^= Overloading
BigInt& BigInt::operator^= (const BigInt &right)
{
    // Declare, initialize variables
    size_t this_size = this->binaryContainer.size();
    size_t right_size = right.binaryContainer.size();

    // Find out which size is larger
    bool this_is_bigger = this_size > right_size;
    size_t container_size = (this_size > right_size) ? this_size : right_size;
    size_t loop_size = (this_size < right_size) ? this_size : right_size;

    // Variables for iterating
    int i = 0;
    std::stringstream out;
    BigInt result;
    result.binaryContainer.resize(container_size);

    // XOR the values that both share
    #pragma omp parallel for
    for (i=0; i < loop_size; i++)
    {
        result.binaryContainer[i] = this->binaryContainer[i] ^ right.binaryContainer[i];
    }// End for

    // XOR the extra values
    // Copy the rest from this
    
    if (this_is_bigger)
    {
    #pragma omp parallel for
        for (i = loop_size; i < this_size; i++)
        {
            result.binaryContainer[i] = this->binaryContainer[i];
        }// End for
    }// End if

    // Copy the rest from right
    else
    {
        #pragma omp parallel for
        for (i = loop_size; i < right_size; i++)
        {
            result.binaryContainer[i] = right.binaryContainer[i];
        }// End for
    }// End else    

    *this = result;
    return *this;
}// End operator^= overloading


// Operator&= Overloading
BigInt& BigInt::operator&= (const BigInt &right)
{
    // Declare, initialize variables
    size_t this_size = this->binaryContainer.size();
    size_t right_size = right.binaryContainer.size();

    // Find out which size is larger
    bool this_is_bigger = this_size > right_size;
    size_t container_size = (this_size > right_size) ? this_size : right_size;
    size_t loop_size = (this_size < right_size) ? this_size : right_size;

    // Variables for iterating
    size_t i = 0;
    std::stringstream out;
    BigInt result;
    result.binaryContainer.resize(container_size);

    // AND the values that both share
    #pragma omp parallel for
    for (i=0; i < loop_size; i++)
    {
        result.binaryContainer[i] = this->binaryContainer[i] & right.binaryContainer[i];
    }// End for

    // AND the extra values
    // Copy the rest from this
    if (this_is_bigger)
    {
        #pragma omp parallel for
        for (i = loop_size; i < this_size; i++)
        {
            result.binaryContainer[i] = this->binaryContainer[i];
        }// End for
    }// End if

    // Copy the rest from right
    else
    {
        #pragma omp parallel for
        for (i = loop_size; i < right_size; i++)
        {
            result.binaryContainer[i] = right.binaryContainer[i];
        }// End for
    }// End else    

    *this = result;
    return *this;
}// End operator&= overloading


/* Comparison Operations */


// Operator== Overloading
bool BigInt::operator== (BigInt &right) const
{
    // Declare, initialize variables
    size_t size = right.binaryContainer.size();
    bool match = true;
    // False if containers don't match size
    if (this->binaryContainer.size() != size)
    {
        match = false;
    }// End if
    if(!match) return match;
    // Loop and check each value
       
    #pragma omp parallel for 
    for (int i = 0; i < size; i++)
    {
        // They don't match
        if (this->binaryContainer[i]!= right.binaryContainer[i])
        {
            match = false;
        }// End if
    }// End for
    
    if(!match) return match;
    size = right.decimalContainer.size();
    if(this->decimalContainer.size() != size){
        match = false;
    }
    if(!match) return match;
    #pragma omp parallel for
    for (size_t i=0; i<size; i++){
        if(strcmp(this->decimalContainer[i].c_str(), right.decimalContainer[i].c_str()))
        {
            match = false;
        }
    }
    // They match
    return match;
}// End operator== overloading



/*** Helpers ***/

// To String Function
std::string BigInt::toString()
{
    // Declare, initialize variables
    std::string result = "";
    size_t size = this->decimalContainer.size();

    #pragma omp parallel for
    for (size_t i = 0; i < size; i++)
    {
        //result += this->container[i].data;
        // As long as you still have data to print
        if (i != size - 1)
        {
            // Fix problem with 5 0's
            if (this->decimalContainer[i] == "0")
            {
                // Change to 5 0's
                this->decimalContainer[i] = "00000";
            }// End if
        }// End if
	#pragma omp critical 
	{
        result.insert(BEGINNING, this->decimalContainer[i]);
	}
    }// End for

    return result;
}// End toString function


string BigInt::divideBy2(string number, string & quotient){
        int x = 0;
        quotient = "";
        const char* derp = number.c_str();
        string thisDigit = "";
        bool begin = true;
        while(*derp != '\0') {
                thisDigit= string(1,*derp);
                if(x != 0){
                        x += atoi(thisDigit.c_str());
                        stringstream s;
                        double temp = x/2;
                        s << floor(temp);
                        quotient += s.str();
                        x = (x%2)*10;
                        begin = false;
                }
                else{
                        if(atoi(thisDigit.c_str())<2){
                                if(!begin){
                                    quotient += "0";
                                }
                                x += 10*atoi(thisDigit.c_str());
                        }
                        else{

                                stringstream s;
                                double value = atoi(thisDigit.c_str())/2;
                                s << (int) floor(value);
                                quotient += s.str();
                                begin = false;
                                if(atoi(thisDigit.c_str())%2){
                                    x = 10;
                                }
                        }
                }
                 derp++;
        }
        return (atoi(thisDigit.c_str())%2)?"1":"0";
}



